#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/7/11 18:19|18:19
# @Author  : yangdingyi
# @File    : 2020-07-11.315. 计算右侧小于当前元素的个数
# @Software: PyCharm
from typing import List


class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        # bisect
        # 二分查找，插入模块。。。
        # import bisect
        # ln = len(nums)
        # que, ans = [], []
        # for i in range(ln-1, -1, -1):
        #     loc = bisect.bisect_left(que, nums[i])
        #     ans.append(loc)
        #     que.insert(loc, nums[i])
        # ans = ans[::-1]
        # return ans
        ans = []

        class Tree:
            class Node:
                def __init__(self, v):
                    self.val = v
                    self.left = None
                    self.right = None

            def __init__(self):
                self.rt = None

            def insert(self, x):
                if self.rt is None:
                    self.rt = self.Node(x)
                    return 0

            def display(self, rt=None, dep=0):
                if not rt:
                    if not self.rt:
                        return
                    self.display(self.rt)
                if rt.right:
                    self.display(rt.right, dep+1)
                print(' '*dep, rt.val)
                if rt.left:
                    self.display(rt.left, dep+1)

        tree = Tree()
        tree.insert(2)
        tree.display()
        return ans


solve = Solution()

questions = [
    ([5, 2, 6, 1],),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print('ans:', solve.countSmaller(q[0]))
